// 分治思想 归并排序
// 在数组中的两个数字，如果前一个数字大于后面的数字，则这两个数字组成一个逆序对
// 就以 arr = [7, 5, 6, 4] 这个例子来讲解为什么一遍归并排序就看可以解决逆序对的问题
// 按照归并排序的思路，会将 arr 分解为 arrL = [7, 5], arrR = [6, 4];
// 继续分解为arrLL = [7], arrLR = [5]; arrRL = [6], arrRR = [4];
// 自此分解完成
// 接下来合并：
// 假设 i 为 arrLL 的数组下标，j 为 arrLR 的数组下标, index 为新数组 res 的下标，初始值都为 0
// 首先 arrLL 与 arrLR 合并，因为 arrLL[i] > arrLR[j]
// 所以可以说明 arrLL 中 7 及其之后的所有数字都大于 arrLR 中的 5
// 也就是说 7 及其之后的所有元素都可以与 5 组成逆序对
// 所以此时 7 及其之后的所有元素个数（leftLen - i）即我们要的逆序对数，需要添加到结果 sum 中
// 即 sum += leftLen - 1
// （这也就是此算法高效的地方，一次可以查找到好多次的逆序对数，而且不会重复）
// 合并之后为 arrL = [5, 7]
// 根据上述方法将 arrRL 和 arrRR 合并为 arrR = [4, 6];
// 现在将 arrL 和 arrR 合并为 arr：
// 5 > 4，说明 5 及其之后的所有元素都能与 4 组成逆序对；所以 sum += (leftLen - 1)；
// 5 < 6，正常排序，不做处理
// 7 > 6，说明7及其之后的所有元素都能与6组成逆序对；所以 sum += (leftLen - 1)；
// 7，正常排序，不作处理
// 最后 sum 就是所有逆序对的总个数

var reversePairs = function (nums) {
  let sum = 0;
  mergeSort(nums);
  return sum;
};

function mergeSort(nums) {
  if (nums.length < 2) return nums;
  let mid = Math.floor(nums.length / 2);
  let left = nums.slice(0, mid);
  let right = nums.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let res = [];
  let leftLen = left.length;
  let rightLen = right.length;
  let len = leftLen + rightLen;
  for (let index = 0, i = 0, j = 0; index < len; index++) {
    if (i >= leftLen) {
      res[index] = right[j++];
    } else if (j >= rightLen) {
      res[index] = left[i++];
    } else if (left[i] <= right[j]) {
      res[index] = left[i++];
    } else {
      res[index] = right[j++];
      sum += leftLen - i;
    }
  }
}

var reversePairs = function (nums) {
  // 归并排序
  let sum = 0;
  mergeSort(nums);
  return sum;

  function mergeSort(nums) {
    if (nums.length < 2) return nums;
    const mid = parseInt(nums.length / 2);
    let left = nums.slice(0, mid);
    let right = nums.slice(mid);
    return merge(mergeSort(left), mergeSort(right));
  }

  function merge(left, right) {
    let res = [];
    let leftLen = left.length;
    let rightLen = right.length;
    let len = leftLen + rightLen;
    for (let index = 0, i = 0, j = 0; index < len; index++) {
      if (i >= leftLen) res[index] = right[j++];
      else if (j >= rightLen) res[index] = left[i++];
      else if (left[i] <= right[j]) res[index] = left[i++];
      else {
        res[index] = right[j++];
        sum += leftLen - i; //在归并排序中唯一加的一行代码
      }
    }
    return res;
  }
};
